package 热题100;

public class Leedcode斐波那契数列 {


    public static int FB(int n){
        if (n == 0){
            return 1;
        }
        if (n == 1){
            return 1;
        }
        return FB(n-1) + FB(n-2);
    }


    public static int dp(int n){
        int [] res = new int[n+1];
        //basecase
        res[0] = 1;
        res[1] = 1;
        for (int i = 2; i < n+1; i++) {
            res[i] = res[i-1] + res[i-2];
        }
        return res[n];
    }

}
